1. Field of the Invention
The present invention relates to communication networks and, more particularly, to a method and apparatus for implementing scheduling algorithms in a network element.
2. Description of the Related Art
Data communication networks may include various computers, servers, nodes, routers, switches, bridges, hubs, proxies, and other network devices coupled together and configured to pass data to one another. These devices will be referred to herein as “network elements.” Data is communicated through the data communication network by passing protocol data units, such as data frames, packets, cells, or segments, between the network elements by utilizing one or more communication links. A particular protocol data unit may be handled by multiple network elements and cross multiple communication links as it travels between its source and its destination over the network.
A network element may have many ports, each of which may maintain multiple data queues. For example, a network element may maintain an ingress queue at an input port for each output port, each flow being handled by that port, or may maintain ingress queues in a number of other manners. Maintaining different queues for different classes or types of traffic allows the network element to treat the different classes of traffic differently. The number of ingress and egress queues will depend on the forwarding scheme being implemented in the network element, i.e., how frames are forward from the ingress ports to the egress ports, and the scheduling algorithm used by the network element.
A scheduling algorithm selects, between queued frames, a particular frame to be handled by the network element. Since frames are queued at the ingress and egress ports, the scheduling algorithm will operate to selectively forward frames from the ingress queues to the egress queues, and from the egress queues onto the network.
Within the network element, it would be desirable to allow a scheduling algorithm to be implemented on a device-wide basis, so that frames received on different ports on the network element may be treated fairly and in accordance with the scheduling algorithm. Unfortunately, this is difficult to implement as it requires communication of information between the ingress ports and egress ports, since frames are queued in both locations. Conventionally, two forwarding schemes have been used to forward frames within a network element from the ingress ports to the egress ports—a push forwarding scheme and a pull forwarding scheme.
With a push forwarding scheme, the ingress ports control how frames are sent to the egress ports, and each ingress port makes determinations independent of the other ingress ports using a local scheduling algorithm. The egress port may also queue frames (using egress queues) and use a scheduling algorithm to decide which frame is to be forwarded next among all locally queued frames. Since there is no device-wide frame scheduling mechanism, it is difficult for a network element to preserve the performance guarantees provided by the individual scheduling algorithms, since the individual schedulers at the ingress queues make local decisions based on only local information.
With a pull forwarding scheme, the egress ports control the transfer of frames from the ingress ports. Since it is usually not economically feasible to provide a scheduler running at the egress port with information about queued frames at the ingress ports, the pull forwarding scheme has usually not allowed for the implementation of scalable network elements that can provide device-wide performance guarantees.